package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/5 11:30
 * @DESCRIPTION
 */
// 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
// 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，
// 但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
// 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，
// 这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
// 输入：s = "101023"
// 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
public class 复原IP地址 {
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    //自己写出  完美通过
    //这题类似于分割回文串，一个判断子串是不是回文串，一个则是判断符合不符合ip的格式要求
    //但是这题退Stringbuiler的使用更熟悉一点，我卡了很多时间在Stringbuilder上面
    public List<String> method1(String s) {
        char[] nums = s.toCharArray();
        recursion(0, nums.length - 1, 1, nums);
        return res;
    }

    //floor用于记录ip的第几段 ip一共有4段
    public void recursion(int start, int end, int floor, char[] nums) {
        if (floor > 4) {
            path.deleteCharAt(path.length() - 1);
            res.add(path.toString());
            path.append(".");
            return;
        }
        for (int i = start; i <= start + 2 && i <= end; i++) {
            //end - i > (4 - floor) * 3
            //这里进行了剪枝操作，如果剩余的数大于ip剩下几段能承接的数，那么必然不符合ip要求
            //method1Aux(start, i, nums)这里判断ip 某一段的数字 是否符合ip要求
            if (!method1Aux(start, i, nums) || end - i > (4 - floor) * 3) {
                continue;
            }
            path.append(new String(nums, start, i - start + 1));
            path.append(".");
            recursion(i + 1, end, floor + 1, nums);
            int temp = path.length();
            //这里的delete(startIndex,endIndex);  他删除的目标不包括下标为endindex
            //详情去测试底下的main方法
            path.delete(temp - (i - start + 1)-1, temp);
        }
    }

    // 判断数字是否符合ip格式要求 0<=  <=255,且除了0外不能以0开头
    public boolean method1Aux(int start, int end, char[] nums) {
        if (nums[start] == '0' && start != end) {
            return false;
        }
        if (end - start == 2) {
            if (nums[start] - '2' > 0
                    || nums[start]== '2'&&nums[start + 1] - '5' > 0
                    || nums[start]=='2'&&nums[start + 1]=='5'&&nums[start+2]-'5'>0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        // StringBuilder sb = new StringBuilder("hello");
        // int temp = sb.length();
        // System.out.println(temp);
        // sb.deleteCharAt(temp);
        // sb.delete(temp-3,temp);
        // System.out.println(sb.toString());
    }
}
